Local area networks (LAN's), are networks of processor-based stations, or nodes, for digitally communicating data. LAN's have several different network topologies. A commonly used topology is the bus, in which all stations are connected to the same cable, i.e., the bus, which is used for transmitting data between any set of two or more stations.
With a bus topology, during a data transmission, there is only a single logical transmission path linking the source and destination stations. Some sort of discipline is needed to ensure that the transmission medium is accessed and used in a fair way.
A widely used bus access scheme is the CSMA/CD (carrier-sense multiple-access, collision detect) scheme. Because the bus is used for transmitting data between any pair of stations, the bus is said to operate in a multiple access mode. All data are transmitted by the sending station first formatting the data in a frame with the address of the destination station in the frame header. The frame is then transmitted on the bus. All stations connected to the bus detect whenever a frame is being transmitted, and when the destination station detects that the frame being transmitted has its own address in the frame header, it continues reading the data in the frame and responds according to a defined link protocol. The header also contains the address of the sending station so that the destination station can respond.
With this system of operation, it is possible for two stations to attempt to transmit a frame over the cable at the same time. If this were permitted to happen, the data would be corrupted. To reduce this possibility, before transmitting a frame, a station listens to the bus to detect if a frame is being transmitted. If it is, i.e., a carrier signal is sensed, the station defers its transmission until the other frame has been transmitted.
Even with carrier sense detection, two stations wishing to transmit a frame may simultaneously determine that there is no current transmission, in which case both attempt to transmit their frames. Also, because of transmission delays, a first station's transmission may not be sensed by a second station. In either case, a "collision" is said to have occurred.
To accommodate the possibility of collisions, as a station transmits its frame onto the bus, it simultaneously monitors the data signal on the bus. If the transmitted and monitored signals are different, a collision is assumed to have been detected. When a station detects a collision, to ensure that the other station is aware of the collision, it sends a random bit pattern for a short period of time known as the jam period. Each station involved then waits for a backoff period before attempting to retransmit its frame. The backoff period is calculated by means of a random function that is statistically expected to generate a different backoff period for each station.
The above-described CSMA/CD bus access scheme is embodied in the IEEE 802.3 standard, where IEEE 802 is the Institute of Electrical and Electronic Engineer's committee 802 on local networking. More specifically, the IEEE 802.3 standard defines the MAC (media access control) sublayer and a corresponding physical layer of the ISO (International Standards Organization) reference model, for connection to a baseband coaxial cable. A well-known example of a CSMA/CD LAN is the Ethernet network, which was developed by Xerox Corporation. The IEEE 802.3 standard is the same as the ISO 8802-3 standard.
Priority under the standard CSMA/CD scheme is "first come, first served" because of the deferment by a transmitter station that detects a carrier sense signal. At least one extension of the CSMA/CD scheme has been developed to permit high priority messages to be more quickly transmitted. One such extension is a linear priority method, which is used after a collision occurs to adjust the backoff time period that a message will wait before a re-transmission is attempted.
A problem with existing priority methods is that high priority messages must wait until a prior message has finished transmitting before obtaining bus access. Also, high priority messages are still susceptible to collisions. Also, if a collision occurs, the bus access time for a high priority message is a function of statistical algorithms and cannot be easily predicted.
It is thus an object of the invention to provide fast bus access times for high priority messages by permitting them to ignore the carrier sense signal. If the high priority message collides with another message already on the bus, sense signal backoff periods are calculated so that for a certain number of re-transmissions, the high priority message has a shorter backoff period than that of a low priority message. Also, an intermediate level of priority is imposed after a high priority message undergoes a predetermined number of collisions. In that case, the message is re-transmitted subject to the carrier sense signal, but with the shorter high priority backoff period. As a result of the invention, bus access time for high priority messages is a deterministic value, which permits response times to high priority events be more easily predicted. Also, in any given LAN network, a station that has a message priority scheme in accordance with the invention is compatible with a station not having such priority. In other words, message priority is established on a per message basis at the transmitting station, and does not interfere with the manner in which the receiving station obtains the message.